package com.sicheng.lc.杂题;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/24 22:52
 */
public class Z函数 {
    /**
     * https://oi-wiki.org/string/z-func/
     * Z 函数（扩展 KMP）
     * 约定：字符串下标以 0 为起点。
     * 对于个长度为 n的字符串s。
     * 定义函数 z[i] 表示s和s[i,n-1] （即以s[i]开头的后缀）的最长公共前缀（LCP）的长度。 被称为  的 Z 函数。
     * <p>
     * z[aaaaa]={0,4,3,2,1}
     * z[aaabaab]={0,2,1,0,2,1,0}
     */

    // 朴素算法
    int[] zTravel(String s) {
        int[] z = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            while (i + z[i] < s.length() && s.charAt(z[i]) == s.charAt(i + z[i]))
                z[i]++;
        }

        return z;
    }

    // 线性算法 z-box
    int[] z(String s) {
        int[] z = new int[s.length()];
        for (int i = 1, l = 0, r = 0; i < s.length(); ++i) {
            if (i <= r && z[i - l] < r - i + 1) {
                z[i] = z[i - l];
            } else {
                z[i] = Math.max(0, r - i + 1);
                while (i + z[i] < s.length() && s.charAt(z[i]) == s.charAt(i + z[i])) ++z[i];
            }
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        return z;
    }
}
